package com.jml.二期.LinkedList002.ext;

public class JmlLinkedList<E> implements JmlList<E> {
    /**
     * 大小
     */
    transient int size = 0;
    /**
     * 链表中第一个元素
     */
    transient JmlLinkedList.Node<E> first;
    /**
     * 链表中最后的元素
     */
    transient JmlLinkedList.Node<E> last;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    @Override
    public E get(int index) {
        return (E)node(index).item;
    }

    JmlLinkedList.Node<E> node(int index) {
        // 如果 当前获取的index <size/2 其实这就是一个折半查找
        if (index < (size >> 1)) {
            // 获取第一个节点
            JmlLinkedList.Node<E> x = first;
            // 从0开始到当前查询下标位置
            for (int i = 0; i < index; i++) {
                // 获取到该元素
                x = x.next;
            }
            return x;
        } else {
            // 获取到最后一个元素
            JmlLinkedList.Node<E> x = last;
            // 从最后一个元素开始遍历到向左遍历
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    @Override
    public E remove(int index) {
        // 获取删除的node节点
        Node<E> node = node(index);
        // 获取当前删除节点的下一个
        Node<E> next = node.next;
        // 获取当前节点删除的上一个
        Node<E> prev = node.prev;
        if (prev == null) {
            // 这说明删除的元素是第一个
            first = next;
        } else {
            prev.next = next;
        }
        if (next == null) {
            // 如果删除当前没有 没有下一个next 说明是最后一个节点，则最后一个节为当前伤处的上一个
            last = prev;
        } else {
            next.prev = prev;
        }
        size--;
        return (E)node;
    }

    void linkLast(E e) {
        // 获取当前最后节点元素
        final JmlLinkedList.Node<E> l = last;
        // 设置新增的node节点元素
        final JmlLinkedList.Node<E> newNode = new JmlLinkedList.Node<>(l, e, null);
        // 最后的节点也就是当前新增的节点
        last = newNode;
        if (l == null) {
            // 说明当前链表是第一次添加元素
            first = newNode;
        } else {
            // 当前下一个节点为 新增的节点
            l.next = newNode;
        }
        size++;
    }

    /**
     * 存放节点元素
     *
     * @param <E>
     */
    private static class Node<E> {
        /**
         * 存放节点元素
         */
        E item;
        /**
         * 下一个节点
         */
        JmlLinkedList.Node<E> next;
        /**
         * 上一个节点
         */
        JmlLinkedList.Node<E> prev;

        // 设置新增的node节点元素
        // final JMLLinkedList.Node<E> newNode = new MayiktLinkedList.Node<>(l, e, null);
        // 上一个节点的last节点也就是下一个的节点的上一个节点（prev）
        Node(JmlLinkedList.Node<E> prev, E element, JmlLinkedList.Node<E> next) {
            // 节点元素
            this.item = element;
            // 下一个元素
            this.next = next;
            // 上一个元素
            this.prev = prev;
        }
    }
}
